package com.ljy.my_study.leetcode.三角形最小路径和;

import java.util.*;

/**
 * @author lijunying
 * @date 2020/7/14 11:20
 */
public class TestMain {
//    给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。
//
//    相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。
//
//             
//
//    例如，给定三角形：
//
//            [
//            [2],
//            [3,4],
//            [6,5,7],
//            [4,1,8,3]
//            ]
//    自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。
//
//             
//
//    说明：
//
//    如果你可以只使用 O(n) 的额外空间（n 为三角形的总行数）来解决这个问题，那么你的算法会很加分。

    public static void main(String[] args) {
        List<List<Integer>> triangle=new ArrayList<>();
        triangle.add(Arrays.asList(2));
        triangle.add(Arrays.asList(3,4));
        triangle.add(Arrays.asList(6,5,7));
        triangle.add(Arrays.asList(4,1,8,3));
        int result=new TestMain().minimumTotal(triangle);
        System.out.println(result);
    }

    public int minimumTotal(List<List<Integer>> triangle) {
        int size=triangle.size();
        Integer[] array=triangle.get(size-1).toArray(new Integer[]{});
        for(int i=triangle.size()-2;i>=0;i--){
            List<Integer> list= triangle.get(i);
            for(int j=0;j<list.size();j++){
                array[j]=Math.min(array[j]+list.get(j),array[j+1]+list.get(j));
            }
        }
        return array[0];
    }

//    public int minimumTotal(List<List<Integer>> triangle) {
//        return doMinimumTotal(triangle,0,0,0,Integer.MAX_VALUE);
//    }
//
//    public int doMinimumTotal(List<List<Integer>> triangle,int level,int index,int sum,int min){
//        if(triangle.size()<=level){
//            return Integer.MAX_VALUE;
//        }
//        if(triangle.get(level).size()<=index){
//            return Integer.MAX_VALUE;
//        }
//        int num=triangle.get(level).get(index);
//        if(triangle.size()==level+1){
//            return Math.min(sum+num,min);
//        }
//        return Math.min(doMinimumTotal(triangle,level+1,index,sum+num,min),
//                doMinimumTotal(triangle,level+1,index+1,sum+num,min));
//    }
}
